1874D - Jellyfish and Miku - CodeForces Solution

#include <bits/stdc++.h>

using i64 = long long;

const double inf = std::numeric_limits<double>::max();

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    std::cout << std::fixed << std::setprecision(12) << "\n";

    int n, m;
    std::cin >> n >> m;

    std::vector<double> f(m + 1, inf), g;
    f[0] = 0;
    for (int i = 0; i < n; ++i) {
        g.assign(m + 1, inf);
        for (int j = 0; j <= m; ++j) {
            for (int k = 1; k * (n - i) + j <= m; ++k) {
                g[j + k] = std::min(g[j + k], f[j] + 1.0 * j / k);
            }
        }
        std::swap(f, g);
    }

    std::cout << n + 2 * f[m] << '\n';

    return 0;
}